Security is an important issue in wireless networks in general and in wireless sensor networks in particular. Nodes used in a wireless sensor network are typically low-cost, battery-powered, and highly resource constrained. Such wireless sensor nodes typically collaborate with each other in order to accomplish various tasks. Security services such as authentication and key management are critical to secure communication between such wireless sensor nodes in hostile environments. As one of the most fundamental security services, pairwise key establishment enables the wireless sensor nodes to communicate securely with each other using cryptographic techniques. However, due to the resource constraints of such wireless sensor nodes, it is typically not feasible for such wireless sensor nodes to use traditional pairwise key establishment techniques such as public key cryptography or a key distribution center.
One approach to addressing such issues in a wireless sensor network employs a key pre-distribution scheme in which each of n nodes in the network store n−1 random keys. Each node in the network uses the keys to determine the authenticity of other nodes in the network. Such an approach is based on the observation that only np pairwise keys are required to be stored in each node of the network to have a connected random graph with high probability. In other words, if each node in the network can store m keys, then the supportable network size (that is, the number of nodes in the network) is n=m/p, where p is the probability that two nodes share a key. However, with such an approach, the size of the network is strictly limited and adding nodes to the network can be an issue. Other approaches that employ a key pre-distribution scheme while attempting to address such issues tend to substantially increase communication costs, especially when multicast groups are established and maintained in such a network.